// standard headers
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>

// boost headers
#include <boost/format.hpp>

// component headers
#include <tree_extract_sub_tree.h>
#include <tree.h>
#define DEBUG_LEVEL 4
#include <debug_func.h>

using std::vector;
using std::string;
using std::max;
using std::replace;
using boost::format;
namespace bcpp_tree_ops
{




//________________________________________________________________________________________

//	op_extract_branches

//		go through a tree and optimize all branches with fewer leaves than max_tree_size

//________________________________________________________________________________________
void op_extract_branches::save_sub_tree(bcpp_tree::t_node& node)
{
	node_UIDs.push_back(node.get_UID());
}


void op_extract_branches::start_at(bcpp_tree::t_node& curr_node)
{
	debug_func_cout(5);
	unsigned child_leaf_count_total = 0;
	float longest_branch_len = 0.0;
	if (!recurse(curr_node, longest_branch_len, child_leaf_count_total) && 
		child_leaf_count_total >= 3)
	{
		save_sub_tree(curr_node);
		inc_branch_count(false);
	}
}

bool op_extract_branches::recurse(bcpp_tree::t_node& curr_node, float& branch_len, unsigned& branch_leaf_count)
{
	debug_func_cout(5);
	branch_len += curr_node.get_length();

	if (curr_node.is_leaf())
	{
		++branch_leaf_count;
		return false;
	}

	// if internal node, get count of all descendent leaves
	//		and add that to the parent's running total
	unsigned cnt_children = curr_node.get_children_count();
	vector<unsigned>	child_leaf_count(cnt_children, 0);
	vector<float> 		child_branch_len(cnt_children, 0.0);
	vector<bool> 		child_extracted(cnt_children, false);
	float longest_branch_len = 0.0;
	bool any_extracted = false;
	unsigned child_leaf_count_total = 0;
	for (unsigned i = 0; i < cnt_children; ++i)
	{
		any_extracted |=
		child_extracted[i] = recurse(	*curr_node.get_child(i),
										child_branch_len[i],
										child_leaf_count[i]
										);
		child_leaf_count_total += child_leaf_count[i];
		longest_branch_len = max(longest_branch_len, child_branch_len[i]);
	}
	branch_leaf_count += child_leaf_count_total;
	branch_len += longest_branch_len;

	// extract the other (substantive) branches if any one branch extracted
	if (any_extracted)
	{
		for (unsigned i = 0; i < cnt_children; ++i)
		{
			// this one is already extracted. Extract the others if necessary
			if (child_extracted[i])
				continue;

			// only extract if > 3
			if (child_leaf_count[i] >= 3)
			{
				save_sub_tree(*curr_node.get_child(i));
				inc_branch_count(last_branch_too_long);
			}

		}
		return true;
	}

	// if reach threshold, extract either the entire branch start with me
	// else if too large, extract each substantive children ( >= 3 ) in turn
	bool too_long = longest_branch_len > max_tree_len;
	if (child_leaf_count_total >= max_tree_size || too_long)
	{
		// would have been optimized because of length
		if (child_leaf_count_total < 3)
			return true;


		// if not so really that large number of children and not too long,
		//		optimize in one clump
		if (child_leaf_count_total <= max_tree_size + 5	&& !too_long)
		{
			save_sub_tree(curr_node);
			inc_branch_count(false);
		}

		else
		// too long or too many
		{
			for (unsigned i = 0; i < cnt_children; ++i)
				// only extract if > 3
				if (child_leaf_count[i] >= 3)
				{
					save_sub_tree(*curr_node.get_child(i));
					inc_branch_count(too_long);
				}
		}
		return true;
	}

	// nothing optimized
	return false;
}
//________________________________________________________________________________________

//	op_nh_strm_post_branch_extract

//________________________________________________________________________________________
void op_nh_strm_post_branch_extract::operator()(bcpp_tree::t_node* root)
{
	if (node_UIDs.count(root->get_UID()))
	{
		nodes.push_back(root);
		os << format("%|1$|;\n")	% sub_tree_name(cnt_sub_trees++);
		assert(cnt_sub_trees == node_UIDs.size());
		return;
	}
	debug_func_cout(5);
	os << '(';
	for (unsigned i = 0; i < root->get_children_count()-1; ++i)
	{
		recurse(root->get_child(i));
		os << ",";
	}
	recurse(root->get_child(root->get_children_count()-1));
	os << ");\n";
	assert(cnt_sub_trees == node_UIDs.size());
}

string op_nh_strm_post_branch_extract::sub_tree_name(unsigned i)
{
	string outstr = boost::str( format("SUB_%|1$6|") % (i + sub_tree_index_offset + 1));
	replace(outstr.begin(), outstr.end(), ' ', 'X');
	return outstr;
}

void op_nh_strm_post_branch_extract::recurse(bcpp_tree::t_node* node)
{
	debug_func_cout(5);
	// if matches sub tree, stop here
	if (node_UIDs.count(node->get_UID()))
	{
		nodes.push_back(node);
        os << format("%|1$|:%|2$.5|")
			   					% sub_tree_name(cnt_sub_trees++)
			   					% node->get_length();
		return;
	}
	unsigned cnt_children = node->get_children_count();

	// is leaf
	if (!cnt_children)
	{
		os << format("%1$s:%2$.5f")
			% node->get_name()
			% node->get_length();
		return;
	}
	os << '(';

	// handle all but last child
	for (unsigned i = 0; i < cnt_children - 1; ++i)
	{
		recurse(node->get_child(i));
		os << ',';
	}

	// handle last child
	recurse(node->get_child(cnt_children-1));

	os << format("):%1$.5f")
			% node->get_length();
}
}
